package com.tojabo.tree;

import java.util.Stack;

import com.tojabo.tree.BinTree.Node;

public class BinTree {

	private Node root;
	
	public BinTree(){
		root=null;
	}
	
	public Node find(int key){
		Node current = root;
		while(current.iData!=key){
			if(key<current.iData){
				current = current.leftChild;
			}else{
				current = current.rightChild;
			}
			if(current == null){
				return null;
			}
		}
		
		return current;
	}
	
	public void insert(int key,double value){
		Node newNode = new Node();
		newNode.iData = key;
		newNode.dData = value;
		
		if(root==null){
			root = newNode;
		}else{
			Node current = root;
			Node parent;
			while(true){
				parent = current;
				if(key<current.iData){ //go left
					current = current.leftChild;
					if(current ==null){
						parent.leftChild = newNode;
						return;
					}
				}//end if go left
				else{
					current = current.rightChild;
					if(current ==null){
						parent.rightChild = newNode;
						return;
					}
				}// end else go right
				
			} //end while
		}
	}
	
	public boolean delete(int key){
		Node current = root;
		Node parent = root;		
		boolean isLeftChild = true;
		
		while(current.iData!=key){
			parent = current;
			if(key<current.iData){ //go left
				isLeftChild = true;
				current = current.leftChild;
			}else{
				isLeftChild = false;
				current = current.rightChild;
			}
			
			if(current==null){
				return false; //didn't find it
			}
		}//end while
		
		//find to delete it		
		if(current.leftChild==null&&current.rightChild==null){
			if(current == root){
				root=null;
			}else if(isLeftChild){
				parent.leftChild = null;
			}else{
				parent.rightChild = null;
			}
		}
		else if(current.rightChild==null){
			if(current==root){
				root = current.leftChild;
			}else if(isLeftChild){
				parent.leftChild = current.leftChild;
			}else{
				parent.rightChild = current.leftChild;
			}
		}
		else if(current.leftChild==null){
			if(current==root){
				root = current.rightChild;
			}else if(isLeftChild){
				parent.leftChild = current.rightChild;
			}else{
				parent.rightChild = current.rightChild;
			}
		}
		else {// both left and right two children 
			Node successor = getSuccessor(current);
			
			if(current==root){
				root = successor;
			}else if(isLeftChild){
				parent.leftChild = successor;
			}else{
				parent.rightChild = successor;
			}
			successor.leftChild = current.leftChild;
		}//end two children
		
		return true;
	}
	
	private Node  getSuccessor(Node delNode){
		
		Node successorParent = delNode;
		Node successor = delNode;
		
		Node current = delNode.rightChild;
		while(current!=null){
			successorParent = successor;
			successor = current;
			current = current.leftChild;
		}
		
		if(successor != delNode.rightChild){
			successorParent.leftChild = successor.rightChild;
			successor.rightChild = delNode.rightChild;
		}
		
		return successor;
	}
	
	public void traverse(int traverseType){
		switch(traverseType){
		case 1: 
			System.out.println("\n Preorder traversal: ");
			preOrder(root);
			break;
		case 2: 
			System.out.println("\n Inorder traversal: ");
			inOrder(root);
			break;
		case 3: 
			System.out.println("\n Postorder traversal: ");
			postOrder(root);
			break;
		}
	}
		
	private void preOrder(Node rootNode) {
		if(rootNode!=null){
			System.out.print(rootNode.iData +",");	
			preOrder(rootNode.leftChild);
			preOrder(rootNode.rightChild);
		}
	}
	
	private void inOrder(Node rootNode) {		
		if(rootNode!=null){
			inOrder(rootNode.leftChild);
			System.out.print(rootNode.iData +",");			
			inOrder(rootNode.rightChild);
		}
	}
	
	private void postOrder(Node rootNode) {		
		if(rootNode!=null){
			postOrder(rootNode.leftChild);
			postOrder(rootNode.rightChild);
			System.out.print(rootNode.iData +",");			
		}
	}
	
	public void displayTree(){
		Stack<Node> globalStack = new Stack<Node>();
		globalStack.push(root);
		int nBlanks =32;
		boolean isRowEmpty =false;
		System.out.println("----------------------------------------");
		
		while(isRowEmpty==false){
			Stack<Node> localStack = new Stack<Node>();
			isRowEmpty = true;
			
			for(int j=0;j<nBlanks;j++){
				System.out.print(' ');
			}
			
			while(!globalStack.isEmpty()){
				Node temp = globalStack.pop();
				if(temp!=null){
					System.out.print(temp.iData);
					
					localStack.push(temp.leftChild);
					localStack.push(temp.rightChild);
					
					if(temp.leftChild!=null||temp.rightChild!=null)
						isRowEmpty=false;
				}else{
					System.out.print("--");
					localStack.push(null);
					localStack.push(null);
				}
				
				for(int j=0;j<nBlanks*2-2;j++){
					System.out.print(' ');
				}
			}//end while globalStack not empty
			
			System.out.println();
			nBlanks /=2;
			
			while(!localStack.isEmpty()){
				globalStack.push(localStack.pop());
			}
		}//while 1
		System.out.println("-----------------------------------------");
		
	}//end displayTree

	class Node {
		public int iData;
		public double dData;
		public Node leftChild;
		public Node rightChild;
		
		public void displayNode(){
			System.out.print("{");
			System.out.print(iData);
			System.out.print(",");
			System.out.print(dData);
			System.out.println("}");
		}
	}
}
